\chapter{Bonus: Let's solve Pell's equation!}
\label{ch:pells_equation}
This is an optional aside, and can be safely ignored.
(On the other hand, it's pretty short.)

\section{Units}
\prototype{$\pm 1$, roots of unity, $3-2\sqrt2$ and its powers.}
Recall according to \Cref{prob:OK_unit_norm} that $\alpha \in \OO_K$ is invertible
if and only if \[ \NK(\alpha) = \pm 1. \]
We let $\OO_K^\times$ denote the set of units of $\OO_K$.

\begin{ques}
	Show that $\OO_K^\times$ is a group under multiplication.
	Hence we name it the \vocab{unit group} of $\OO_K$.
\end{ques}

What are some examples of units?
\begin{example}
	[Examples of units in a number field]
	\listhack
	\begin{enumerate}
		\ii $\pm 1$ are certainly units, present in any number field.

		\ii If $\OO_K$ contains a root of unity $\omega$ (i.e.\ $\omega^n=1$),
		then $\omega$ is a unit.
		(In fact, $\pm 1$ are special cases of this.)

		\ii Of course, not all units of $\OO_K$ are roots of unity.
		For example, if $\OO_K = \ZZ[\sqrt3]$ (from $K = \QQ(\sqrt3)$) then
		the number $2+\sqrt3$ is a unit, as its norm is
		\[ \NK(2+\sqrt3) = 2^2 - 3 \cdot 1^2 = 1. \]
		Alternatively, just note that the inverse $2-\sqrt3 \in \OO_K$ as well:
		\[ \left( 2-\sqrt3 \right)\left( 2+\sqrt3 \right) = 1. \]
		Either way, $2-\sqrt3$ is a unit.

		\ii Given any unit $u \in \OO_K^\times$, all its powers are also units.
		So for example, $(3-2\sqrt2)^n$ is always a unit of $\ZZ[\sqrt2]$, for any $n$.
		If $u$ is not a root of unity, then this generates infinitely many new units in $\OO_K^\times$.
	\end{enumerate}
\end{example}

\begin{ques}
	Verify the claims above that
	\begin{enumerate}[(a)]
		\ii Roots of unity are units, and
		\ii Powers of units are units.
	\end{enumerate}
	One can either proceed from the definition
	or use the characterization $\NK(\alpha) = \pm 1$.
	If one definition seems more natural to you, use the other.
\end{ques}

\section{Dirichlet's unit theorem}
\prototype{The units of $\ZZ[\sqrt3]$ are $\pm(2+\sqrt3)^n$.}

\begin{definition}
	Let $\mu(\OO_K)$ denote the set of roots of unity
	contained in a number field $K$ (equivalently, in $\OO_K$).
\end{definition}
\begin{example}[Examples of $\mu(\OO_K)$]
	\listhack
	\begin{enumerate}[(a)]
		\ii If $K = \QQ(i)$, then $\OO_K = \ZZ[i]$. So
		\[ \mu(\OO_K) = \{\pm1, \pm i\} \quad\text{where } K = \QQ(i). \]
		\ii If $K = \QQ(\sqrt3)$, then $\OO_K = \ZZ[\sqrt 3]$. So
		\[ \mu(\OO_K) = \{\pm 1\} \quad\text{where } K = \QQ(\sqrt 3). \]
		\ii If $K = \QQ(\sqrt{-3})$, then $\OO_K = \ZZ[\half(1+\sqrt{-3})]$.
		So
		\[ \mu(\OO_K)
			= \left\{ \pm 1, \frac{\pm 1 \pm \sqrt{-3}}{2} \right\}
			\quad\text{where } K = \QQ(\sqrt{-3})
		\]
		where the $\pm$'s in the second term need not depend on each other;
		in other words $\mu(\OO_K) = \left\{ z \mid z^6=1 \right\}$.
	\end{enumerate}
\end{example}
\begin{exercise}
	Show that we always have that $\mu(\OO_K)$
	comprises the roots to $x^n-1$ for some integer $n$.
	(First, show it is a finite group under multiplication.)
\end{exercise}

We now quote, without proof, the so-called Dirichlet's unit theorem,
which gives us a much more complete picture of what the units in $\OO_K$ are.
Legend says that Dirichlet found the proof of this theorem
during an Easter concert in the Sistine Chapel.
\begin{theorem}
	[Dirichlet's unit theorem]
	Let $K$ be a number field with signature $(r_1, r_2)$ and set
	\[ s = r_1 + r_2 - 1. \]
	Then there exist units $u_1$, \dots, $u_s$ such that every unit
	$\alpha \in \OO_K^\times$ can be written \emph{uniquely} in the form
	\[ \alpha = \omega \cdot u_1^{n_1} \dots u_s^{n_s} \]
	for $\omega \in \mu(\OO_K)$ is a root of unity,
	and $n_1, \dots, n_s \in \ZZ$.
\end{theorem}
More succinctly:
\begin{moral}
We have $\OO_K^\times \cong \ZZ^{r_1+r_2-1} \times \mu(\OO_K)$.
\end{moral}
A choice of $u_1$, \dots, $u_s$ is called a choice of \vocab{fundamental units}.

Here are some example applications.
\begin{example}
	[Some unit groups]
	\listhack
	\begin{enumerate}[(a)]
		\ii Let $K = \QQ(i)$ with signature $(0,1)$.
		Then we obtain $s = 0$, so Dirichlet's Unit theorem says that there are no
		units other than the roots of unity.
		Thus
		\[ \OO_K^\times = \{\pm 1, \pm i\} \quad\text{where } K = \QQ(i). \]
		This is not surprising,
		since $a+bi \in \ZZ[i]$ is a unit if and only if $a^2+b^2 = 1$.

		\ii Let $K = \QQ(\sqrt 3)$, which has signature $(2,0)$.
		Then $s=1$, so we expect exactly one fundamental unit.
		A fundamental unit is $2+\sqrt3$ (or $2-\sqrt3$, its inverse) with norm $1$, and so we find
		\[ \OO_K^\times = \left\{ \pm (2+\sqrt3)^n \mid n \in \ZZ \right\}.  \]

		\ii Let $K = \QQ(\sqrt[3]{2})$ with signature $(1,1)$.
		Then $s=1$, so we expect exactly one fundamental unit.
		The choice $1 + \sqrt[3]{2} + \sqrt[3]{4}$. So
		\[ \OO_K^\times
			= \left\{ \pm \left( 1+\sqrt[3]{2}+\sqrt[3]{4} \right)^n \mid n \in \ZZ \right\}. \]
	\end{enumerate}
\end{example}

I haven't actually shown you that these are fundamental units,
and indeed computing fundamental units is in general hard.

\section{Finding fundamental units}
Here is a table with some fundamental units.
\[
	\begin{array}{rl}
		d & \text{Unit} \\ \hline
		d=2 & 1+\sqrt 2 \\
		d=3 & 2+\sqrt3 \\
		d=5 & \half(1+\sqrt5) \\
		d=6 & 5+2\sqrt6 \\
		d=7 & 8+3\sqrt7 \\
		d=10 & 3+\sqrt{10} \\
		d=11 & 10+3\sqrt11
	\end{array}
\]

In general, determining fundamental units is computationally hard.

However, once I tell you what the fundamental unit is, it's not too bad
(at least in the case $s=1$) to verify it.
For example,
suppose we want to show that $10 + 3\sqrt{11}$ is a fundamental unit of $K = \QQ(\sqrt 11)$,
which has ring of integers $\ZZ[\sqrt{11}]$.
If not, then for some $n > 1$, we would have to have
\[ 10 + 3 \sqrt{11} = \pm \left( x+y\sqrt{11} \right)^n. \]
For this to happen, at the very least we would need $\left\lvert y \right\rvert < 3$.
We would also have $x^2-11y^2 = \pm 1$.
So one can just verify (using $y= 1,2$) that this fails.

The point is that: Since $(10,3)$ is the \emph{smallest}
(in the sense of $\left\lvert y \right\rvert$)
integer solution to $x^2-11y^2 = \pm 1$, it must be the fundamental unit.
This holds more generally, although in the case that $d \equiv 1 \pmod 4$
a modification must be made as $x$, $y$ might be half-integers (like $\half(1+\sqrt5)$).
\begin{theorem}
	[Fundamental units of Pell's equations]
	Assume $d$ is a squarefree integer.
	\begin{enumerate}[(a)]
		\ii If $d \equiv 2,3 \pmod 4$,
		and $(x,y)$ is a minimal integer solution to $x^2-dy^2 = \pm 1$,
		then $x + y \sqrt d$ is a fundamental unit.
		\ii If $d \equiv 1 \pmod 4$,
		and $(x,y)$ is a minimal \emph{half-integer} solution to $x^2-dy^2 = \pm 1$,
		then $x + y \sqrt d$ is a fundamental unit.
		(Equivalently, the minimal integer solution to $a^2 - db^2 = \pm 4$
		gives $\half (a + b \sqrt d)$.)
	\end{enumerate}
	(Any reasonable definition of ``minimal'' will work, such as sorting by $\left\lvert y \right\rvert$.)
\end{theorem}

\section{Pell's equation}
This class of results completely eradicates Pell's Equation.
After all, solving
\[ a^2 - d \cdot b^2 = \pm 1 \]
amounts to finding elements of $\ZZ[\sqrt d]$ with norm $\pm 1$.
It's a bit weirder in the $d \equiv 1 \pmod 4$ case, since in that case $K = \QQ(\sqrt d)$
gives $\OO_K = \ZZ[\half(1+\sqrt d)]$, and so the fundamental unit may not actually be a solution.
(For example, when $d = 5$, we get the solution $(\half, \half)$.)
Nonetheless, all \emph{integer} solutions are eventually generated.

To make this all concrete, here's a simple example.
\begin{example}[$x^2-5y^2 = \pm 1$]
	Set $K = \QQ(\sqrt 5)$, so $\OO_K = \ZZ[\half(1+\sqrt 5)]$.
	By Dirichlet's unit theorem, $\OO_K^\times$ is generated by a single element $u$.
	The choice
	\[ u = \frac 12 + \frac 12 \sqrt 5 \]
	serves as a fundamental unit,
	as there are no smaller integer solutions to $a^2-5b^2=\pm 4$.

	The first several powers of $u$ are
	\[
	\begin{array}{rrr}
		\renewcommand{\arraystretch}{1.4}
		n & \multicolumn{1}{c}{u^n} & \text{Norm} \\ \hline
		-2 & \half(3-\sqrt5) & 1 \\
		-1 & \half (1-\sqrt5) & -1 \\
		0 & 1 & 1 \\
		1 & \half(1+\sqrt5) & -1 \\
		2 & \half(3+\sqrt5) & 1 \\
		3 & 2 + \sqrt 5 & -1 \\
		4 & \half(7+3\sqrt5) & 1 \\
		5 & \half(11+5\sqrt5) & -1 \\
		6 & 9 + 4\sqrt 5 & 1
	\end{array}
	\]
	One can see that the first integer solution is $(2,1)$, which gives $-1$.
	The first solution with $+1$ is $(9,4)$.
	Continuing the pattern, we find that every third power of $u$ gives an integer solution
	(see also \Cref{prob:unit_cubed}),
	with the odd ones giving a solution to $x^2-5y^2=-1$ and
	the even ones a solution to $x^2-5y^2=+1$.
	All solutions are generated this way, up to $\pm$ signs
	(by considering $\pm u^{\pm n}$).
\end{example}

\section\problemhead
\begin{problem}[Fictitious account of the battle of Hastings]
	Determine the number of soldiers in the following battle:
	\begin{quote}
		The men of Harold stood well together,
		as their won{}t was, and formed thirteen squares,
		with a like number of men in every square thereof, and woe
		to the hardy Norman who ventured to enter their redoubts;
		for a single blow of Saxon war-hatched would break his lance
		and cut through his coat of mail . . .
		when Harold threw himself into the fray the Saxons
		were one might square of men, shouting the battle-cries,
		``Ut!'', ``Olicrosse!'', ``Godemite!''
	\end{quote}
	% The answer can be found by hand.
	% You may assume that the army has size at least $1$ and
	% at most one billion.
\end{problem}
\begin{problem}
	\label{prob:unit_cubed}
	Let $d > 0$ be a squarefree integer,
	and let $u$ denote the fundamental unit of $\QQ(\sqrt d)$.
	Show that either $u \in \ZZ[\sqrt d]$,
	or $u^n \in \ZZ[\sqrt d] \iff 3 \mid n$.
\end{problem}
\begin{problem}
	Show that there are no integer solutions to
	\[ x^2 - 34y^2 = -1 \]
	despite the fact that $-1$ is a quadratic residue mod $34$.
\end{problem}
